/*
 * Project: Sudoku Hint Engine for Android
 * Copyright (C) 2010-2013 Emanuel Moecklin
 * 
 * Available under the terms of the Lesser General Public License (LGPL)
 */
package com.onegravity.sudoku.solver.rules.wing;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.Map;
import java.util.Set;

import com.onegravity.sudoku.solver.HintResource;
import com.onegravity.sudoku.solver.R;
import com.onegravity.sudoku.solver.accumulator.HintsAccumulator;
import com.onegravity.sudoku.solver.accumulator.StopHintProductionException;
import com.onegravity.sudoku.solver.core.IndirectHint;
import com.onegravity.sudoku.solver.core.IndirectHintProducer;
import com.onegravity.sudoku.solver.data.Cell;
import com.onegravity.sudoku.solver.data.Grid;
import com.onegravity.sudoku.solver.data.Region;
import com.onegravity.sudoku.solver.util.BitSetFactory;
import com.onegravity.sudoku.solver.util.Permutations;

/**
 * W-Wing
 * @author Emanuel Moecklin
 */
public class WWingProducer implements IndirectHintProducer {

    public WWingProducer() {}

    private class WingFinderResult {
    	private Cell cellB;
    	private Cell cellC;
    	private Region region;
    }
    
    @Override
    public void getHints(Grid grid, HintsAccumulator accu) throws StopHintProductionException, InterruptedException {
    	// (1) find potential WX cells
    	Map<String, ArrayList<Cell>> potentialWXCells = new HashMap<String, ArrayList<Cell>>(); 
        for (int yPos=0; yPos<9; yPos++) {
            if (Thread.interrupted()) throw new InterruptedException();
            for (int xPos=0; xPos<9; xPos++) {
            	Cell cell = grid.getCell(xPos, yPos);
            	BitSet candidates = cell.getPotentialValues();
            	if (candidates.cardinality()==2) {
                	int w = candidates.nextSetBit(0);
                	int x = candidates.nextSetBit(w+1);
                	String key = Integer.toString(w) + Integer.toString(x);
                	ArrayList<Cell> cells = potentialWXCells.get(key);
                	if (cells==null) cells = new ArrayList<Cell>();
                	cells.add(cell);
                	potentialWXCells.put(key, cells);
            	}
            }
        }
        
        // (2) check all potential WX cell pairs for a W-Wing pattern
        for (String key:potentialWXCells.keySet()) {
        	ArrayList<Cell> cells = potentialWXCells.get(key);
        	if (cells.size()<2) continue;
			int w = Character.digit(key.charAt(0), 10);
			int x = Character.digit(key.charAt(1), 10);
            Permutations perm = new Permutations(2, cells.size());
            while (perm.hasNext()) {
                if (Thread.interrupted()) throw new InterruptedException();
                int[] indicesArray = perm.nextBitNums();
                Cell cellA = cells.get(indicesArray[0]);
                Cell cellD = cells.get(indicesArray[1]);
                if (cellA.isNeighbor(cellD)) continue;	// if the two cells see each other then we have a naked pair
                // (3) check for W-Wing with WX
                WingFinderResult wing = findWing(grid, cellA, cellD, w, x);
                if (wing!=null) {
                	// found W-Wing(s)
                	IndirectHint hint = new WWingHint(cellA, wing.cellB, wing.cellC, cellD, w, x, wing.region, getRemovablePotentials(cellA, cellD, w));
                	if (hint.isWorth()) accu.add(hint);
                }
                // (4) now check for W-Wing with XW
                wing = findWing(grid, cellA, cellD, x, w);
                if (wing!=null) {
                	// found W-Wing(s)
            		IndirectHint hint = new WWingHint(cellA, wing.cellB, wing.cellC, cellD, x, w, wing.region, getRemovablePotentials(cellA, cellD, x));
                	if (hint.isWorth()) accu.add(hint);
                }
            }
        }
    }

    /**
     * Finds a W-Wing from cell A and cell D and the given w/x values.
     * Cell A (wx) -> Cell B (...x) ==> Cell C (...x) -> Cell D (wx)
     * -> means weak link, ==> means strong link
     */
    private WingFinderResult findWing(Grid grid, Cell cellA, Cell cellD, int w, int x) {
    	// (1) find cell B that sees cell A and has x as a candidate
		BitSet positions = new BitSet(10);
    	for (Cell cellB:cellA.getHouseCells()) {
    		if (cellB.hasPotentialValue(x)) {
    			// (2) find cell C that has a strong link to cell B on digit x
    			for (Region region:grid.getRegionsAt(cellB)) {
					region.getPotentialPositions(positions, x);
    				if (positions.cardinality()==2) {
    					// (3) strong link found, now check if cell C sees cell D
    					int index1 = positions.nextSetBit(0);
    					int index2 = positions.nextSetBit(index1+1);
    					Cell tmp = region.getCell(index1);
    					Cell cellC = (tmp.equals(cellB)) ? region.getCell(index2) : tmp;
    					if (cellD.isNeighbor(cellC)) {
			        		// W-Wing found!
    						WingFinderResult result = new WingFinderResult();
			        		result.cellB = cellB;
			        		result.cellC = cellC;
			        		result.region = region;
			        		return result;	// we only need two cells B/C to make this a W-Wing
    					}
    				}
    			}
    		}
    	}
    	return null;
    }
    
    private Map<Cell,BitSet> getRemovablePotentials(Cell cellA, Cell cellD, int w) {
        // Build list of removable potentials
        Map<Cell,BitSet> removablePotentials = new HashMap<Cell,BitSet>();
        Set<Cell> victims = new LinkedHashSet<Cell>(cellA.getHouseCells());
        victims.retainAll(cellD.getHouseCells());
        for (Cell cell:victims) {
            if (cell.hasPotentialValue(w))
                removablePotentials.put(cell, BitSetFactory.createOneElement(w));
        }
        return removablePotentials;
    }

	@Override
	public String getProducerName() {
		return HintResource.getString(R.string.producer_w_wings);
	}
}